package bTree.LeetCode;

import java.util.Arrays;
import java.util.Stack;

public class 下一个更大元素2 {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, -1);
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for (int i = 1; i < n; i++) {
            if (nums[stack.peek()] >= nums[i]) {
                stack.push(i);
            } else {
                while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                    dp[stack.pop()] = nums[i];
                }
                stack.push(i);
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[stack.peek()] >= nums[i]) {
                stack.push(i);
            } else {
                while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                    dp[stack.pop()] = nums[i];
                }
                stack.push(i);
            }
        }
        return dp;

    }
}